/**
 * @program: LeetCode
 * @description: LeetCode :
 * @author: WXY
 * @create: 2022-12-30 11:52
 * @Version 1.0
 **/


public class offer_thirteen2_maximalRectangle {
    public static int maximalRectangle(String[] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length();
        int[][] left = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i].charAt(j) == '1') {
                    left[i][j] = (j == 0 ? 0 : left[i][j - 1]) + 1;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i].charAt(j) == '0') {
                    continue;
                }
                int width = left[i][j];
                int area = width;
                for (int k = i - 1; k >= 0; k--) {
                    width = Math.min(width, left[k][j]);
                    area = Math.max(area, width * (i - k + 1));
                }
                ans = Math.max(ans, area);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        String[] str = {"10100", "10111", "11111", "10010"};
        int i = maximalRectangle(str);
        System.out.println(i);
    }

}
